package arithmetic.LeetCode;

import static utils.ListNodeUtils.createLink;
import static utils.ListNodeUtils.printLink;

import org.junit.jupiter.api.Test;

import utils.ListNodeUtils.ListNode;

/**
 * 19. 删除链表的倒数第 N 个结点
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
 * <p>
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 *
 * @author jiangfeng on 2023/4/10
 */
public class RemoveNthNode {

    @Test
    public void test(){
        ListNode link = createLink(new int[] {1, 2, 3, 4, 5});
        printLink(link);
        printLink(removeNthFromEnd(link,2));

    }





    /*
     * <p>
     * 两个方法:
     * 1.传统方法就是:
     * 遍历两遍, 第一遍计算长度L,第二遍到第 L-n+1个是开始删的(删除L-n的next)
     * 2.双指针法:
     * 先让头指针走n步,再加入尾指针, 等头指针到了尾结点,尾指针则处于所处位置,即可一遍循环删除.
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode result = head;
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        head = result;
        for (int i = 0; i < len-n-1; i++) {
            head = head.next;
        }
        head.next = null;
        return result;
    }

    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode result = head;
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        head = result;
        for (int i = 0; i < len-n-1; i++) {
            head = head.next;
        }
        head.next = null;
        return result;
    }
}
